Hashing functions are widely used to accelerate finding items in a large database. Typically, the hashing function output is an index for a location in memory where the entry matched with the hashing input may be stored. The size of memory space indexed by the hashing output is much smaller than the cardinality of input space. Hashing is used to assign pseudo-randomly generated input entries to particular locations in a finite memory space. The memory utilization is maximized when the rate of hashing collisions is minimized. A hashing collision occurs when multiple different hashing inputs result in the same hashing output value. Assuming the input distribution is uniform, it is desired to have uniform hashing output distribution to minimize the probability of a hashing collision.
One example use for a hashing function is routing table lookup in a network switch. Network switches use hashing functions to store and find routing information. Consider an IPv6 network switch which can store 64 k entries in a routing table. Each routing table entry consists of an IPv6 destination address paired with a forwarding port. The location of an entry in the routing table is identified by the hashing function output produced when an IPv6 destination address is input to the hashing function. When a packet arrives at the network switch, the hashing function output is computed based on the IPv6 destination address input extracted from the packet. The hashing function output provides the index for a routing table entry which may contain the matching IPv6 address. In this particular example, the hashing input is the 128-bit wide IPv6 destination address and the hashing output is 16-bit wide index that points to a location in the 64 k-entry routing table. In other words, the hashing function is a mapping from a 128-bit input to a 16-bit output.
In network switch applications, the bit width of the input to the hashing function can be very large when routing rules consist of many tuples such as MAC addresses, IPv6 addresses, TCP port numbers, etc. In the OpenFlow standard, for example, the network switch flow rule requires a hashing input of more than 600 bits. Meanwhile, the hashing function throughput requirement for network switch applications is very stringent in order to search flow routing rules fast enough to keep pace with the incoming packet traffic rate. For example, a network switch with 64 instances of 10 Gbps ports requires nearly 1 billion table look-ups per second. It is highly desirable to have a uniform hashing output distribution in order to maximize memory space utilization with minimum hashing collisions.
One popular conventional hashing technique is based on XOR (exclusive-OR) operations. As previously indicated, a hashing function is a mapping between an n-bit input and an m-bit output. Typically, the input bit width n is much larger than the output bit width m (n>>m). Let x be the 1×n vector of hashing input bits, and let y be the 1×m vector of hashing output bits. The XOR hashing output y is obtained by GF(2) (Galois field 2) multiplication of the input vector x and an n×m binary matrix H, as shown belowy=x·H  (1)
where “·” indicates vector-matrix GF(2) multiplication. The binary matrix H is called the hashing matrix.
The XOR-based hashing represented by (1) above can be implemented in hardware using XOR logic. Let x(a) be the a-th bit of the vector x, H(a, b) the (a, b) component of the hashing matrix H, H(:, b) the b-th column of H, and H(a, :) the a-th row of H. Each bit of the output vector y is obtained by XORing selected bits in the input vector x. The XOR input selection for the i-th bit of y, y(i), is dictated by non-zero bit positions of the i-th column of H, H(:, i). For example, if H(1,i)=H(4, i)=H(7,i)=1, while all other components of H(:, i) are zero, then y(i) is obtained by XORing x(1), x(4) and x(7).
In many practical systems, it is important for the hashing matrix H to be programmable, so the hashing function can be updated according to input statistics. In some applications, H can be randomly chosen for security purposes. Typically, H is programmed during system initialization. In order to program the n×m binary matrix H, n×m bits are required in programming memory space.
If H is permitted to be an arbitrary n×m binary matrix, then the XOR-based hashing function can be implemented as shown in FIG. 1. In this conventional architecture, the hashing matrix H is an arbitrary n×m binary matrix, and the hashing output is obtained according to (1) above. When the 1×n input vector x is very large, however, the FIG. 1 architecture disadvantageously requires a correspondingly large programming memory space (n×m bits to program H). Also, the architecture has considerable complexity, because each bit of the 1×m output vector y requires an XOR tree with n input bits. Note that the select logic of FIG. 1 combines every bit in input vector x with every bit in a corresponding row of hashing matrix H.
The desirability of hashing large bit-width inputs to produce a uniform output distribution, and with low complexity, low programming memory space, low latency and high throughput, is evident in view of the foregoing.